package com.yc.sort;

/**
 * @author yc
 *
 */
public class SimpleSort {
	/**
	 * 小数上浮
	 * @param array
	 */
	public void maopao_small(Integer[] array) {
		Integer temp;
		Integer n = array.length;
		
		for(int i = n-1; i > 0; i--) {
			for (int j = n-1; j > (n-i-1); j--) {
				System.out.println("i=" + i + ", j=" + j);
				if (array[j] < array[j-1]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
				}
			}
		}
	}
	/**
	 * 优化版
	 * @param array
	 */
	public void maopao_small2(Integer[] array) {
		Integer temp;
		Integer n = array.length;
		
		for(int i = 1; i <= n-1; i++) {//刷新一次末端位置（控制结束）（末端一直在增加）
			boolean exchange = false;
			for (int j = n-1; j >= i; j--) {//刷新
				System.out.println("i=" + i + ", j=" + j);
				if (array[j] < array[j-1]) {
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
					exchange = true;
				}
			}
			if (exchange) {
				break;
			}
		}
	}
	
	/**
	 * 大数下沉
	 * @param array
	 */
	public void maopao_big(Integer[] array) {
		Integer temp;
		Integer n = array.length;
		
		for(int i = n-2; i >= 0; i--) {//刷新一次末端位置（控制结束）(末端一直在缩小)
			for (int j = 0; j <= i; j++) {//从小到大刷新（从上到下）
				System.out.println("i=" + i + ", j=" + j);
				if (array[j] < array[j+1]) {
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}
	
	/**
	 * 冒泡排序-标准答案[属于“大数下沉”]
	 * @param source
	 */
	public void bubbleSort(int[] source) {
		for (int i= source.length-1; i > 0; i++) {// max -->  1
			for (int j = 0; j < i; j ++) {// 0 --> [max -->  1]-1
				swap(source, j, j+1);
			}
		}
	}
	
	/**
	 * 选择排序-标准答案
	 * 从前到后，一个一个和它后面的所有数比较，确保比较的当前数字是最小的
	 * @param source
	 */
	public void selectSort(int[] source) {
		for (int i = 0; i < source.length-1; i++) {
			for (int j = i+1; j < source.length; j++) {
				if (source[i] > source[j]) {
					swap(source, i, j);
				}
			}
		}
	}
	
	//插入排序
	public void insertSort1(int[] source) {
		int n = source.length;
		for (int i=1; i <= n-1; i++) {//要交换的数字
			int temp = source[i];
			for (int j = i-1; j >= 0; j--) {//被交换的（已排序的最大数）
				System.out.println("i=" + i + ", j=" + j);
				if (source[j] > temp) {
					
					source[j+1] = source[j];
					if (j == 0) {
						source[j] = temp;
					}
				} else {
					source[j+1] = temp;
					break;
				}
			}
		}
	}
	
	public void insetSort(int[] source) {
		for (int i = 1; i < source.length; i ++) {
			for (int j = i; (j > 0) && source[j] < source[j-1]; j--) {
				swap(source, j, j-1);
			}
		}
	}
	
	
	//交换数组source里下标为x和y到两个元素
	private void swap(int[] source, int x, int y) {
		int temp = source[x];
		source[x] = source[y];
		source[y] = temp;
	}
	
	/**
	 * shell(希尔)排序【插入排序的一种】
	 * @param source
	 * @param index
	 */
	public void shellSort(int[] source) {
		int index = source.length;//排序长度
		int Temp;//暂存变量
		boolean Change;//数据是否改变
		int DataLength;//分割集合的间隔长度
		int Pointer;//进行处理的位置
		
		DataLength = (int) index / 2;//初始集合间隔长度
		
		while(DataLength != 0) {//数列仍可以分割
			//对各个集合进行处理
			for (int j = DataLength; j < index; j++) {
				Change = false;
				Temp = source[j];//暂存Data[j]值，带交换值
				Pointer = j - DataLength;//计算进行处理的位置
				
				//进行集合内树枝的比较与交换值
				while(Temp < source[Pointer] && Pointer >= 0 && Pointer <= index) {
					source[Pointer + DataLength] = source[Pointer];
					//计算下一个欲进行处理的位置
					Pointer = Pointer - DataLength;
					Change = true;
					if (Pointer < 0 || Pointer > index) {
						break;
					}
				}
				
				//与最后的数值交换
				source[Pointer + DataLength] = Temp;
				
				if (Change) {
					//打印目前的排序结果
					System.out.println("排序中：");
					for (int l = 0; l < source.length; l++) {
						System.out.printf("%3s ", source[l]);
					}
					System.out.println("");
				}
					
			}
			DataLength = DataLength / 2;//计算下次分割的间隔长度
			
		}
		
		
	}
	
	/**
	 * 二分法
	 * 从左至右排序，使左边的排序队列不断增多，每次获取右边下一个数字，然后把这个数字插入左边已经
	 * 排好的队列中：找到插入的位置，把该位置至最大已排队列都向右移动一位。关键使如何找到这个位置
	 * 方式就是对左边已排队列进行二分查找，找到下一个数字应该所属的位置
	 * @param source
	 */
	public void binarySort(int[] source) {
		int low, high, mid=0;
		int temp;
		for (int i = 1; i < source.length; i++) {
			temp = source[i];
			low = 0;
			high = i - 1;
			while(low <= high) {
				mid = (low + high)/2;
				if (source[mid] > temp)
					high = mid - 1;
				else 
					low = mid + 1;
				
			}
			for (int j = i - 1; j > high; j--)
				source[j + 1] = source[j];
			source[high + 1] = temp;
			
			System.out.print("i=" + i + ", low=" + low + ", mid=" + mid + ", higih=" + high  + " | ");
			pintsource(source);
		}
		
//		for (int i = 0; i < source.length; i++) {
//			System.out.printf("%d ", source[i]);
//		}
	}
	
	/**
	 * 快速排序
	 * @param source
	 */
	public void quickSort(int[] source, int low, int high) {
		int i, j, x;
		if (low < high) {
			i = low;
			j = high;
			x = source[i];
			while (i < j) {
				while (i < j && source[j] > x) {
					j--;
				}
				if (i < j) {
					source[i] = source[j];
					i++;
				}
				while (i < j && source[i] < x) {
					i++;
				}
				if (i < j) {
					source[j] = source[i];
					j--;
				}
			}
			source[i] = x;
			pintsource(source);
			quickSort(source, low, i-1);
			quickSort(source, i + 1, high);
		}
		
		
	}
	
	public void merge(int[] source, int start1, int end1, int start2, int end2) {
		
		int i,j;//i,j分别为表1，表2的游标
		i = start1;
		j = start2;
		
		int k = 0;
		//建立一个临时长度为两个子列表长度之和的数组
		int[] temp = new int[end2 - start1 + 1];
		
		//通过循环，依次从两个子列表中找到较大的元素放入临时数组中
		while (i <= end1 && j <= end2) {
			if (source[i] > source[j]) {
				temp[k++] = source[j++];
			} else {
				temp[k++] = source[i++];
			}
		}
		
		//把剩下的元素依次放入临时数组中（肯定使只剩下一方）
		while (i <= end1) {
			temp[k++] = source[i++];
		}
		while (j <= end2) {
			temp[k++] = source[j++];
		}
		
		//把合并好的数字写回去
		k = start1;
		for (int ele : temp) {
			source[k++] = ele;
		}
		
	}
	
	/**
	 * 归并排序
	 * 思想：二分法 分而治之
	 * @param source
	 * @param start
	 * @param end
	 */
	public void mergeSort(int[] source, int start, int end) {
		if (start < end) {
			int mid = (start + end)/2;
			//两路归并
			mergeSort(source, start, mid);
			mergeSort(source, mid + 1, end);
			merge(source, start, mid, mid + 1, end);
			
			//多路归并
//			int mid = (start + end)/4;
//			mergeSort(source,start,1*mid);
//			mergeSort(source,1*mid+1,2*mid);
//			mergeSort(source,2*mid+1, 3*mid);
//			mergeSort(source,3*mid+1, end);
//			
//			merge(source,start,1*mid, 1*mid+1, 2*mid);
//			merge(source,2*mid+1,3*mid, 3*mid+1, end);
//			merge(source,start,2*mid, 2*mid+1, end);
		}
	}
	
	
	private void pintsource(int[] source) {
		for (int i : source) {
			System.out.print(i + ", ");
		}
		System.out.println("");
	}
	
	

	public static void main(String[] args) {
		SimpleSort ss = new SimpleSort();
		
		int[] array = new int[] {9,3,8,2,9,2,7,6,8,15};
//		ss.maopao_big(array);
//		ss.selectSort(array);
//		ss.insertSort1(array);
//		ss.insetSort(array);
//		ss.shellSort(array);
//		ss.binarySort(array);
//		ss.quickSort(array, 0, array.length-1);
		ss.mergeSort(array, 0, array.length-1);
		
		for (int i : array) {
			System.out.println(i);
		}
		

	}

}
